package LearnDataStructure.a_线性结构.例题;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-03 18:01
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 */

import java.util.HashSet;

/**
 * 给定一个有环链表，实现一个算法返回环路的开头结点
 *
 * 有环链表的定义：
 * 在链表中某个结点的next元素指向在它前面出现过的节点，则表明该链表存在环路
 * */
public class f_单向有环链表查找环起始节点 {
    public static void main(String[] args) {
        f_单向有环链表查找环起始节点 test = new f_单向有环链表查找环起始节点();
        int[] arr = new int[] {1,2,3,4,5};
        test.useCheckBegin(arr);
        test.useCheckBegin2(arr);
    }

    public void useCheckBegin(int[] arr) {
        CaseNode head = new CaseNode(arr[0]);
        CaseNode p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new CaseNode(arr[i]);
            p = p.next;
        }
        //造环
        p.next = head.next;
        //造的环是：
        /*
        A  > B  > C  > D  > E
            ^               |
            |_______________|
         */
        CaseNode begin = checkBegin(head);
        System.out.println(begin.data);
        // System.out.println(hasCircle(head));
    }

    public CaseNode checkBegin(CaseNode head) {
        CaseNode p = head;
        HashSet set = new HashSet();
        while (p != null) {
            if (set.contains(p)) {
                return p;
            } else {
                set.add(p);
                p = p.next;
            }
        }
        return null;
    }







    public void useCheckBegin2(int[] arr) {
        CaseNode head = new CaseNode(arr[0]);
        CaseNode p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new CaseNode(arr[i]);
            p = p.next;
        }
        //造环
        p.next = head.next;
        //造的环是：
        /*
        A  > B  > C  > D  > E
            ^               |
            |_______________|
         */
        CaseNode begin = checkBegin2(head);
        System.out.println(begin.data);
    }

    /**
     * 要求不开辟新的空间
     * 要求提高性能
     * 这个方法适用于明确有环，而且这个环有柄
     * 如果无柄，那么就没有“环起始节点”这个说法了。全环链表每一个节点都可以看作是起始节点。
     * O(N)
     * @param head
     * @return
     */
    public CaseNode checkBegin2(CaseNode head) {
        CaseNode slow = head;
        CaseNode fast = head;
        while (true) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        CaseNode p = head;
        while (true) {
            p = p.next;
            slow = slow.next;
            if (p == slow) {
                break;
            }
        }
        return p;
    }

    public boolean hasCircle(CaseNode head) {
        CaseNode slow = head;
        CaseNode fast = head;
        while (true) {
            if (fast.next == null || fast == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
    }


}
